package com.leetcode.partition3;

import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/8 17:26
 */
public class LC295数据流的中位数 {

    private static class MedianFinder {

        //大于中位数的小顶堆
        private PriorityQueue<Integer> minHeap;
        //小于中位数的大顶堆
        private PriorityQueue<Integer> maxHeap;

        public MedianFinder() {
            minHeap = new PriorityQueue<>(Integer::compare);
            maxHeap = new PriorityQueue<>(((o1, o2) -> Integer.compare(o2, o1)));
        }

        public void addNum(int num) {
            if (minHeap.isEmpty() || num > minHeap.peek()) {
                minHeap.offer(num);
                if (minHeap.size() > maxHeap.size() + 1) {
                    maxHeap.offer(minHeap.poll());
                }
            } else {
                maxHeap.offer(num);
                if (maxHeap.size() > minHeap.size()) {
                    minHeap.offer(maxHeap.poll());
                }
            }
        }

        public double findMedian() {
            int m = minHeap.size(), n = maxHeap.size();
            if ((m + n) % 2 == 1) return minHeap.peek();
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        }
    }
}
